package com.cat.dynamicPlanning02;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-cost-for-cutting-cake-i/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/11/5 15:58
 * @since JDK17
 */

public class Solution38 {
    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        PriorityQueue<Integer> h1 = new PriorityQueue<>((a, b) -> b - a), h2 = new PriorityQueue<>((a, b) -> b - a);
        Arrays.stream(horizontalCut).forEach(h1::add);
        Arrays.stream(verticalCut).forEach(h2::add);
        int ans = 0, h = 1, v = 1;
        while (!h1.isEmpty() || !h2.isEmpty()) {
            if (h2.isEmpty() || (!h1.isEmpty() && h1.peek() > h2.peek())) {
                ans += h * h1.poll();
                v++;
            } else {
                ans += v * h2.poll();
                h++;
            }
        }

        return ans;
    }
}
